/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "TJU",
    /* First member's full name */
    "Student",
    /* First member's email address */
    "student@tju.edu.cn",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave bla······nk if none) */
    ""
};

/*
 * 空闲块和已分配块的结构：
 * 已分配块由一个头部和一个脚部组成：头部和脚部包含块的大小和分配位。
 * 空闲块由一个头部，一个前驱指针和一个后继指针组成。空闲块的头部和脚部包含块的大小和分配位。
 *
 * 空闲链表的组织方式：
 * 使用分离空闲链表（segregated free lists），每个链表包含特定大小范围的空闲块。
 * 空闲链表的头指针存储在一个数组中，每个数组元素指向一个空闲链表的头部。
 *
 * 分配器如何操作空闲链表：
 * 初始化：创建初始的空闲链表，并扩展堆以包含一个初始空闲块。
 * 分配：在适当的空闲链表中查找合适的空闲块，如果找到则分割块并返回，否则扩展堆。
 * 释放：将已分配块标记为空闲，并尝试合并相邻的空闲块，然后将块插入到适当的空闲链表中。
 * 重新分配：调整已分配块的大小，如果需要，分配新的块并复制数据，然后释放旧块。
 */

//单字或双字对齐
#define ALIGNMENT 8

// 将大小向上舍入到ALIGNMENT的最接近倍数
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

//基本常量和宏定义
#define WSIZE               4                              
#define DSIZE               8                          
#define CHUNKSIZE           (1<<9)                      
#define FREE_LIST_NUM       11                          
#define MAX(x, y)           ((x) > (y) ? (x) : (y))     
#define MIN(x, y)           ((x) < (y) ? (x) : (y))     

//将大小和分配位打包到一个字中
#define PACK(size, alloc)   ((size) | alloc) 

//读写一个字
#define GET(p)              (*(unsigned int*)(p))
#define PUT(p, val)         (*(unsigned int*)(p) = (unsigned int)(val))

//从地址p读取大小和分配字段
#define GET_SIZE(p)         (GET(p) & ~0x7)
#define GET_ALLOC(p)        (GET(p) & 0x1)

//给定块指针bp，计算头和脚的地址
#define HDRP(bp)            ((char*)(bp) - WSIZE)
#define FTRP(bp)            ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

//给定块指针bp，计算下一个和前一个块的地址
#define NEXT_BLKP(bp)       ((char*)(bp) + GET_SIZE(((char*)(bp) - WSIZE)))
#define PREV_BLKP(bp)       ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE)))

//分离空闲块的前驱和后继指针
#define PREV_PTR(bp)        ((char*)(bp))
#define NEXT_PTR(bp)        ((char*)(bp) + WSIZE)

//分离空闲链表的头指针
#define HEAD_PTR(i)         ((char*)(heap_list) + (i) * WSIZE) 

//给定空闲块指针bp，获取前驱和后继块的地址
#define GET_PREV(bp)        ((char*)GET(PREV_PTR(bp)))
#define GET_NEXT(bp)        ((char*)GET(NEXT_PTR(bp)))

//给定索引i，获取空闲链表的头指针
#define GET_HEAD(i)         ((char*)GET((heap_list) + (i) * WSIZE))

//堆的起始地址
static char* heap_list;

static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void *place(void* bp, size_t asize);
static void *coalesce(void* bp);
static int getindex(int size);
static void insert(void* bp);
static void delete(void* bp);
static int check_free_list(int index);
static int check_block(char* bp);
static void printlist();
static size_t get_size(size_t size);

/*
 * get_size - 将请求的大小转换为实际的块大小
 * 最小空闲块大小为16字节，保证块大小为8的倍数
 */
static size_t get_size(size_t size)
{
    size_t asize;
    //最小空闲块大小为16字节
    if(size <= DSIZE)
    {
        asize = 2 * DSIZE;
    }
    //保证块大小为8的倍数
    else
    {
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
    }
    return asize;
}

/*
 * printlist - 打印空闲链表
 */
static void printlist()
{
    for(int i = 0; i < FREE_LIST_NUM; i++)
    {
        char* temp = GET_HEAD(i);
        printf("the %d list: ", i);
        while(temp)
        {
            printf(" the prev of %p is %p", temp, GET_PREV(temp));
            temp = GET_NEXT(temp);
        }
        printf("\n");
    }
}

/*
 * check_free_list - 检查空闲链表的一致性
 */
static int check_free_list(int index)
{
    char* temp = GET_HEAD(index);
    char* prev = NULL;
    size_t size = 1 << (index + 4); 
    while(temp)
    {
        //检查块是否在正确的大小类中
        if(GET_SIZE(HDRP(temp)) >= size || GET_SIZE(HDRP(temp)) < ( size >> 1) )
        {
            printf("the size of %d block is wrong !!\n", index);
            return 0;
        }
        //检查块是否被分配
        if(GET_ALLOC(HDRP(temp)) != 0)
        {
            printf("the %d block is not free !!\n", index);
            return 0;
        }
        //检查块的前驱指针是否正确
        if(GET_PREV(temp) != prev)
        {
            printf("the prev pointer of %d block is wrong !!\n", index);
            return 0;
        }
        prev = temp;
        temp = GET_NEXT(temp);
    }
    return 1;
}

/*
 * check_block - 检查块的一致性
 */
static int check_block(char* bp)
{
    //检查块的头尾是否一致
    if(GET(HDRP(bp)) != GET(FTRP(bp)))
    {
        printf("the header and footer of %p is not equal !!\n", bp);
        return 0;
    }
    //检查块的大小是否是8的倍数
    if(GET_SIZE(HDRP(bp)) % 8)
    {
        printf("the size of %p is not a multiple of 8 !!\n", bp);
        return 0;
    }
    return GET_ALLOC(HDRP(bp));
}

/*
 * getindex - 获取空闲链表的索引
 */
static int getindex(int size)
{
    for(int i = 0; i < FREE_LIST_NUM; i++)
    {
        //最小的类为16字节
        if(size <= (1 << (i + 4)))
        {
            return i;
        }
    }
    return FREE_LIST_NUM - 1;
}

/*
 * insert - 将空闲块插入到适当的空闲链表中
 */
static void insert(void* bp)
{
    size_t size = GET_SIZE(HDRP(bp));
    int index = getindex(size);
    char* head = GET_HEAD(index);
    //如果该链表为空，则让头指针指向该块
    if(head == NULL)
    {
        PUT(HEAD_PTR(index), bp);
        PUT(PREV_PTR(bp), NULL);
        PUT(NEXT_PTR(bp), NULL);
    }
    //如果该链表不为空，则插入到链表的头部
    else
    { 
        PUT(PREV_PTR(head), bp);
        PUT(NEXT_PTR(bp), head);
        PUT(PREV_PTR(bp), NULL);
        PUT(HEAD_PTR(index), bp);
    }
}

/*
 * delete - 从空闲链表中删除空闲块
 */
static void delete(void* bp)
{
    size_t size = GET_SIZE(HDRP(bp));
    int index = getindex(size);
    char* head = HEAD_PTR(index);
    //第一种情况：前空后空
    if(GET_PREV(bp) == NULL
     &&GET_NEXT(bp) == NULL)
    {
        PUT(head, NULL);
    }
    //第二种情况：前空后不空
    else if(GET_PREV(bp) == NULL
          &&GET_NEXT(bp) != NULL)
    {
        PUT(head, GET_NEXT(bp));
        PUT(PREV_PTR(GET_NEXT(bp)), NULL);
    }
    //第三种情况：前不空后空
    else if(GET_PREV(bp) != NULL
          &&GET_NEXT(bp) == NULL)
    {
        PUT(NEXT_PTR(GET_PREV(bp)), NULL);
    }
    //第四种情况：前不空后不空
    else
    {
        PUT(NEXT_PTR(GET_PREV(bp)), GET_NEXT(bp));
        PUT(PREV_PTR(GET_NEXT(bp)), GET_PREV(bp));
    }
}

/*
 * find_fit - 在空闲链表中寻找合适的块（首次适配）
 */
static void* find_fit(size_t asize)
{
    int index = getindex(asize);
    for(int i = index; i < FREE_LIST_NUM; i ++)
    {
        char* temp = GET_HEAD(i);
        while(temp != NULL)
        {
            if(GET_SIZE(HDRP(temp)) >= asize)
            {
                return temp;
            }
            temp = GET_NEXT(temp);
        }
    }
    return NULL;
}

/*
 * place - 放置并切割块
 */
static void *place(void* bp, size_t asize)
{
    size_t size = GET_SIZE(HDRP(bp));
    size_t rsize = size - asize;
    //如果该块未分配，则从空闲链表中删除
    if(!GET_ALLOC(HDRP(bp)))
    {
        delete(bp);
    }
    //如果剩余空间足够，则分割块
    if (rsize >= (2 * DSIZE))
    {
        //前边的块空闲，后边的块分配
        if(asize >= 96)
        {
            PUT(HDRP(bp),PACK(rsize,0));
            PUT(FTRP(bp),PACK(rsize,0));
            PUT(HDRP(NEXT_BLKP(bp)),PACK(asize,1));
            PUT(FTRP(NEXT_BLKP(bp)),PACK(asize,1));
            insert(bp);
            return NEXT_BLKP(bp);
        }
        //前边的块分配，后边的块空闲
        else
        {
            PUT(HDRP(bp),PACK(asize,1));
            PUT(FTRP(bp),PACK(asize,1));
            PUT(HDRP(NEXT_BLKP(bp)),PACK(rsize,0));
            PUT(FTRP(NEXT_BLKP(bp)),PACK(rsize,0));
            insert(NEXT_BLKP(bp));
        }
    }
    //如果剩余空间不够，则整块分配
    else 
    {
        PUT(HDRP(bp),PACK(size,1));
        PUT(FTRP(bp),PACK(size,1));
    }
    return bp;
}

/*
 * coalesce - 合并空闲块
 */
static void* coalesce(void* bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
    //第一种情况：前分配后分配
    if (prev_alloc == 1
     && next_alloc == 1) 
    { 
        insert(bp);
        return bp;
    }
    //第二种情况：前分配后空闲
    else if (prev_alloc == 1
          && next_alloc == 0) 
    {
        delete(NEXT_BLKP(bp));
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    //第三种情况：前空闲后分配
    else if (prev_alloc == 0
          && next_alloc == 1) 
    { 
        delete(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp); 
    }
    //第四种情况：前空闲后空闲
    else if (prev_alloc == 0
          && next_alloc == 0)
    { 
        delete(NEXT_BLKP(bp));
        delete(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
                GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    insert(bp);
    return bp;
}

/*
 * extend_heap - 扩展堆
 */
static void* extend_heap(size_t words)
{
    char *bp;
    size_t size;

    //保证块大小为双字
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
    {
        return NULL;
    }
    //初始化新的空闲块
    PUT(HDRP(bp), PACK(size, 0));           
    PUT(FTRP(bp), PACK(size, 0));           
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));   
    //合并之前的空闲块
    return coalesce(bp);
}

/*
 * mm_check - 检查堆的一致性
 */
int mm_check()
{
    //序言块
    char* bp = HEAD_PTR(12);
    //遍历堆
    for(;GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if(!check_block(bp))
        {
            return 0;
        }
    }
    //检查空闲链表
    for(int i = 0; i < FREE_LIST_NUM; i ++)
    {
        if(!check_free_list(i))
        {
           printlist();
           return 0;
        }
    }
    return 1;
}

/*
 * mm_init - 初始化内存分配器
 */
int mm_init(void)
{
    //初始化堆
    if ((heap_list = mem_sbrk( (FREE_LIST_NUM + 3) * WSIZE)) == (void *)-1)
    {
        return -1;
    }
    //初始化空闲链表
    for(int i = 0; i < FREE_LIST_NUM; i++)
    {
        PUT(HEAD_PTR(i), NULL);
    }
    //初始化序言块和结尾块
    PUT(HEAD_PTR(FREE_LIST_NUM), PACK(DSIZE, 1));  
    PUT(HEAD_PTR(FREE_LIST_NUM + 1), PACK(DSIZE, 1));  
    PUT(HEAD_PTR(FREE_LIST_NUM + 2), PACK(0, 1));      
    //扩展堆
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
    {   
        return -1;
    }
    //mm_check();
    return 0;
}


/*
 * mm_malloc - 分配内存块
 */
void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char* bp;
    if(size == 0)
    {
        return NULL;
    }

    asize = get_size(size);
    //遍历空闲链表，寻找合适的块
    if((bp = find_fit(asize)) != NULL)
    {
        
        bp = place(bp, asize);
        //mm_check();
        return bp;
    }

    //如果找不到合适的块，则扩展堆
    extendsize = MAX(asize, CHUNKSIZE);
    if((bp = extend_heap(extendsize/WSIZE)) == NULL)
    {
        return NULL;
    }
    //将新的块放入空闲链表
    bp = place(bp, asize);
    //mm_check();
    return bp;
}

/*
 * mm_free - 释放内存块
 */
void mm_free(void *bp)
{
    if(bp == NULL)
    {
        return;
    }
    size_t size = GET_SIZE(HDRP(bp));
    //标记bp为空闲块，并且合并
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
    //mm_check();
}

/*
 * mm_realloc - 重新分配内存块
 */
void *mm_realloc(void *ptr, size_t size)
{
    //如果ptr为空，则调用malloc函数
    if(ptr == NULL)
    {
        return mm_malloc(size);
    }
    //如果size为0，则调用free函数
    if(size == 0)
    {
        mm_free(ptr);
        return NULL;
    }

    //计算新的size
    size_t new_size = get_size(size);
    size_t old_size = GET_SIZE(HDRP(ptr));

    //如果新的size小于等于原来的size，则直接返回ptr
    if(old_size == new_size)
    {
        return ptr;
    }
    
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
    size_t next_size = GET_SIZE(HDRP(NEXT_BLKP(ptr)));
    size_t total_size = old_size;
    char* next_ptr = NEXT_BLKP(ptr);
    char* newptr;

    //如果下一个块是空闲块，并且合并后的大小大于等于新的size，则直接合并
    if(!next_alloc && (next_size + old_size >= new_size) )
    {
        total_size += next_size;
        delete(next_ptr);
        PUT(HDRP(ptr), PACK(total_size, 1));
        PUT(FTRP(ptr), PACK(total_size, 1));
        ptr = place(ptr,total_size);
    }
    //如果后面是结尾块，则直接扩展堆
    else if(!next_size && new_size >= old_size)
    {
        size_t extend_size = new_size - old_size;
        if((long)(mem_sbrk(extend_size)) == -1)
        {   
            return NULL;
        }
        PUT(HDRP(ptr), PACK(total_size + extend_size, 1));
        PUT(FTRP(ptr), PACK(total_size + extend_size, 1));
        PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1));
        ptr = place(ptr, new_size);
    }
    //否则，只能重新分配内存
    else
    {
        newptr = mm_malloc(new_size);
        if(newptr == NULL)
        {
            return NULL;
        }
        memcpy(newptr, ptr, MIN(old_size, size));
        mm_free(ptr);
        return newptr;
    }
    return ptr;
}














